package algorithm.sort;

public class Quick3WaysSort implements Sort {
    @Override
    public String name() {
        return "快速排序";
    }

    @Override
    public void sort(Integer[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    //对区间[l,r]数组进行排序
    private void sort(Integer[] arr, int l, int r) {
        //说明之后一个元素，
        if (r-l<=7) {
            insertionSort(arr,l,r);
            return;
        }
        partition(arr, l, r);

    }

    //寻找出下标p，使p左边的元素小于p，右边的元素大于p
    private void partition(Integer[] arr, int l, int r) {
        //stand 标准元素，使元素位于stand 2边
        int stand = arr[l];


        int lt =l;          //[lt,gt]    = stand
        int gt =r+1;        //[gt+1,r]   > stand
        int i = l+1;        //[l+1,lt-1] < stand
        while (i<gt){
            if (arr[i]<stand){
                swap(arr,lt,i);
                i++;
                lt++;
            }else if (arr[i]>stand){
                swap(arr,gt,i);
                gt--;
            }else{
                i++;
            }

        }

    }



    private void insertionSort(Integer[] arr, int l, int r){
        for (int i = l+1; i <=r; i++) {
            for (int j = i; j >l ; j--) {
                if (arr[j]<arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }







    public void swap(Integer[] arr,int i , int j){
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
}
